<!doctype html>
<html class="no-js" lang="en">
  <head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>
    
  2.5. Map - LinkedHashSet & LinkedHashMap源码解析 - 
  
  </title>
 <meta name="description" content="">
 <link href="atom.xml" rel="alternate" title="" type="application/atom+xml">
    <link rel="stylesheet" href="asset/css/foundation.min.css" />
    <link rel="stylesheet" href="asset/css/docs.css" />

    <script src="asset/js/vendor/modernizr.js"></script>
    <script src="asset/js/vendor/jquery.js"></script>
    <script src="asset/highlightjs/highlight.pack.js"></script>
    <link href="asset/highlightjs/styles/github.css" media="screen, projection" rel="stylesheet" type="text/css">
    <script>hljs.initHighlightingOnLoad();</script>
    
  </head>
  <body class="antialiased hide-extras">
    
    <div class="marketing off-canvas-wrap" data-offcanvas>
      <div class="inner-wrap">


<nav class="top-bar docs-bar hide-for-small" data-topbar>

<div id="header">
    <h1><a href="index.html"></a></h1>
</div>

</nav>
        <nav class="tab-bar show-for-small">
  <a href="javascript:void(0)" class="left-off-canvas-toggle menu-icon">
    <span> &nbsp; </span>
  </a>
</nav>

<aside class="left-off-canvas-menu">
      <ul class="off-canvas-list">
      <li><a href="index.html">Home</a></li>
      
        <li class="divider"></li>
        <li><label>1. Java 基础</label></li>

          
            <li><a title="1. Java 基础" href="16923474457318.html">1. Java 基础</a></li>
          

      
        <li class="divider"></li>
        <li><label>2. JCF（Java 集合）</label></li>

          
            <li><a title="2. JCF（Java 集合）" href="16923736135980.html">2. JCF（Java 集合）</a></li>
          
            <li><a title="2.4. Map - HashSet & HashMap 源码解析" href="16924335832240.html">2.4. Map - HashSet & HashMap 源码解析</a></li>
          
            <li><a title="2.5. Map - LinkedHashSet & LinkedHashMap源码解析" href="16924372183713.html">2.5. Map - LinkedHashSet & LinkedHashMap源码解析</a></li>
          
            <li><a title="2.6. Map - TreeSet & TreeMap 源码解析" href="16925007307182.html">2.6. Map - TreeSet & TreeMap 源码解析</a></li>
          

      
        <li class="divider"></li>
        <li><label>mysql</label></li>

          
            <li><a title="事务隔离" href="16925938083498.html">事务隔离</a></li>
          

      
        <li class="divider"></li>
        <li><label>常见文档</label></li>

          
            <li><a title="Paxos选举算法" href="16926055818559.html">Paxos选举算法</a></li>
          

      
      </ul>
    </aside>

<a class="exit-off-canvas" href="#"></a>

        <section id="main-content" role="main" class="scroll-container">

          <div class="row">
            <div class="large-3 medium-3 columns">
              <div class="hide-for-small">
                <div class="sidebar">
                <nav>
                  <ul id="side-nav" class="side-nav">

                    
                      <li class="side-title"><span>1. Java 基础</span></li>
                        
                          <li><a title="1. Java 基础" href="16923474457318.html">1. Java 基础</a></li>
                        

                    
                      <li class="side-title"><span>2. JCF（Java 集合）</span></li>
                        
                          <li><a title="2. JCF（Java 集合）" href="16923736135980.html">2. JCF（Java 集合）</a></li>
                        
                          <li><a title="2.4. Map - HashSet & HashMap 源码解析" href="16924335832240.html">2.4. Map - HashSet & HashMap 源码解析</a></li>
                        
                          <li><a title="2.5. Map - LinkedHashSet & LinkedHashMap源码解析" href="16924372183713.html">2.5. Map - LinkedHashSet & LinkedHashMap源码解析</a></li>
                        
                          <li><a title="2.6. Map - TreeSet & TreeMap 源码解析" href="16925007307182.html">2.6. Map - TreeSet & TreeMap 源码解析</a></li>
                        

                    
                      <li class="side-title"><span>mysql</span></li>
                        
                          <li><a title="事务隔离" href="16925938083498.html">事务隔离</a></li>
                        

                    
                      <li class="side-title"><span>常见文档</span></li>
                        
                          <li><a title="Paxos选举算法" href="16926055818559.html">Paxos选举算法</a></li>
                        

                    
                  </ul>
                </nav>
                </div>
              </div>
            </div>
            <div class="large-9 medium-9 columns">

 <div class="markdown-body">
<h1>2.5. Map - LinkedHashSet & LinkedHashMap源码解析</h1>

<ul>
<li>
<a href="#toc_0">2.5.1. Java 7 - LinkedHashSet&amp;Map</a>
<ul>
<li>
<a href="#toc_1">addEntry()代码如下:</a>
</li>
<li>
<a href="#toc_2">remove()</a>
</li>
</ul>
</li>
<li>
<a href="#toc_3">2.4.2. LinkedHashSet</a>
</li>
<li>
<a href="#toc_4">2.4.3. 案例：基于LinkedHashMap实现的FIFO缓存器</a>
</li>
</ul>


<h2 id="toc_0">2.5.1. Java 7 - LinkedHashSet&amp;Map</h2>

<p>如果了解 HashSet 和 HashMap，一定能够想到 LinkedHashSet 和 LinkedHashMap 其实也是一回事。LinkedHashSet 和 LinkedHashMap 在Java里也有着相同的实现，前者仅仅是对后者做了一层包装，也就是说LinkedHashSet里面有一个LinkedHashMap(适配器模式)。因此本文将重点分析LinkedHashMap。</p>

<p>LinkedHashMap实现了Map接口，即允许放入key为null的元素，也允许插入value为null的元素。从名字上可以看出该容器是linked list和HashMap的混合体，也就是说它同时满足HashMap和linked list的某些特性。可将LinkedHashMap看作采用linked list增强的HashMap。</p>

<p><img src="media/16924372183713/16924384631488.jpg" alt=""/></p>

<p>事实上 LinkedHashMap 是 HashMap 的直接子类，二者唯一的区别是 LinkedHashMap 在 HashMap 的基础上，采用双向链表(doubly-linked list)的形式将所有entry连接起来，这样是为保证元素的迭代顺序跟插入顺序相同。</p>

<p>上图给出了LinkedHashMap的结构图，主体部分跟HashMap完全一样，多了header指向双向链表的头部，该双向链表的迭代顺序就是entry的插入顺序。</p>

<pre><code>/**
 * The head (eldest) of the doubly linked list.
 */
transient LinkedHashMap.Entry&lt;K,V&gt; head;

/**
 * The tail (youngest) of the doubly linked list.
 */
transient LinkedHashMap.Entry&lt;K,V&gt; tail;
</code></pre>

<p>除了可以保迭代历顺序，这种结构还有一个好处 : 迭代LinkedHashMap时不需要像HashMap那样遍历整个table，而只需要直接遍历header指向的双向链表即可，也就是说LinkedHashMap的迭代时间就只跟entry的个数相关，而跟table的大小无关。</p>

<p>有两个参数可以影响LinkedHashMap的性能: 初始容量(inital capacity)和负载系数(load factor)。初始容量指定了初始table的大小，负载系数用来指定自动扩容的临界值。当entry的数量超过capacity*load_factor时，容器将自动扩容并重新哈希。</p>

<p>对于插入元素较多的场景，将初始容量设大可以减少重新哈希的次数。将对象放入到LinkedHashMap或LinkedHashSet中时，有两个方法需要特别关心: hashCode()和equals()。hashCode()方法决定了对象会被放到哪个bucket里，当多个对象的哈希值冲突时，equals()方法决定了这些对象是否是“同一个对象”。所以，如果要将自定义的对象放入到LinkedHashMap或LinkedHashSet中，需要@Override hashCode()和equals()方法。</p>

<p><B>相关方法和HashMap的逻辑几乎一样，在HashMap的基础上添加了列表的维护。</B></p>

<h3 id="toc_1">addEntry()代码如下:</h3>

<pre><code>// LinkedHashMap.addEntry()
void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size &gt;= threshold) &amp;&amp; (null != table[bucketIndex])) {
        resize(2 * table.length);// 自动扩容，并重新哈希
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = hash &amp; (table.length-1);// hash%table.length
    }
    // 1.在冲突链表头部插入新的entry
    HashMap.Entry&lt;K,V&gt; old = table[bucketIndex];
    Entry&lt;K,V&gt; e = new Entry&lt;&gt;(hash, key, value, old);
    table[bucketIndex] = e;
    // 2.在双向链表的尾部插入新的entry
    e.addBefore(header);
    size++;
}


/**
 * 将新entry e插入到双向链表头引用header的前面，这样e就成为双向链表中的最后一个元素
 */
private void addBefore(Entry&lt;K,V&gt; existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}
</code></pre>

<h3 id="toc_2">remove()</h3>

<p>remove(Object key) 的作用是删除key值对应的entry，该方法的具体逻辑是在removeEntryForKey(Object key)里实现的。removeEntryForKey()方法会首先找到key值对应的 entry，然后删除该 entry (修改链表的相应引用)。查找过程跟 get() 方法类似。<br/>
注意，这里的删除也有两重含义:</p>

<pre><code>- 从table的角度看，需要将该entry从对应的bucket里删除，如果对应的冲突链表不空，需要修改冲突链表的相应引用。
- 从header的角度来看，需要将该entry从双向链表中删除，同时修改链表中前面以及后面元素的相应引用。
</code></pre>

<p><img src="media/16924372183713/16924390113636.jpg" alt=""/></p>

<p>removeEntryForKey()对应的代码如下:</p>

<pre><code>// LinkedHashMap.removeEntryForKey()，删除key值对应的entry
final Entry&lt;K,V&gt; removeEntryForKey(Object key) {
    ......
    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);// hash&amp;(table.length-1)
    Entry&lt;K,V&gt; prev = table[i];// 得到冲突链表
    Entry&lt;K,V&gt; e = prev;
    while (e != null) {// 遍历冲突链表
        Entry&lt;K,V&gt; next = e.next;
        Object k;
        if (e.hash == hash &amp;&amp;
            ((k = e.key) == key || (key != null &amp;&amp; key.equals(k)))) {// 找到要删除的entry
            modCount++; size--;
            // 1. 将e从对应bucket的冲突链表中删除
            if (prev == e) table[i] = next;
            else prev.next = next;
            // 2. 将e从双向链表中删除
            e.before.after = e.after;
            e.after.before = e.before;
            return e;
        }
        prev = e; e = next;
    }
    return e;
}
</code></pre>

<h2 id="toc_3">2.4.2. LinkedHashSet</h2>

<p>前面已经说过LinkedHashSet是对LinkedHashMap的简单包装，对LinkedHashSet的函数调用都会转换成合适的LinkedHashMap方法，因此LinkedHashSet的实现非常简单，这里不再赘述。</p>

<pre><code>public class LinkedHashSet&lt;E&gt;
    extends HashSet&lt;E&gt;
    implements Set&lt;E&gt;, Cloneable, java.io.Serializable {
    ......
    // LinkedHashSet里面有一个LinkedHashMap
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        map = new LinkedHashMap&lt;&gt;(initialCapacity, loadFactor);
    }
    ......
    public boolean add(E e) {//简单的方法转换
        return map.put(e, PRESENT)==null;
    }
    ......
}
</code></pre>

<h2 id="toc_4">2.4.3. 案例：基于LinkedHashMap实现的FIFO缓存器</h2>

<p>java.util.LinkedHashMap#removeEldestEntry 方法的作用是告诉Map是否要删除“最老”的Entry，所谓最老就是当前Map中最早插入的Entry，如果该方法返回true，最老的那个元素就会被删除。</p>

<p>在每次插入新元素的之后LinkedHashMap会自动询问removeEldestEntry()是否要删除最老的元素。这样只需要在子类中重载该方法，当元素个数超过一定数量时让removeEldestEntry()返回true，就能够实现一个固定大小的FIFO策略的缓存。示例代码如下:</p>

<pre><code>class FIFOCache&lt;K, V&gt; extends LinkedHashMap&lt;K, V&gt;{
    private final int cacheSize;
    public FIFOCache(int cacheSize){
        this.cacheSize = cacheSize;
    }

    // 当Entry个数超过cacheSize时，删除最老的Entry
    @Override
    protected boolean removeEldestEntry(Map.Entry&lt;K,V&gt; eldest) {
       return size() &gt; cacheSize;
    }
}
</code></pre>


</div>

<br /><br />
<hr />

<div class="row clearfix">
  <div class="large-6 columns">
	<div class="text-left" style="padding:15px 0px;">
		
	        <a href="16924335832240.html"  title="Previous Post: 2.4. Map - HashSet & HashMap 源码解析">&laquo; 2.4. Map - HashSet & HashMap 源码解析</a>
	    
	</div>
  </div>
  <div class="large-6 columns">
	<div class="text-right" style="padding:15px 0px;">
		
	        <a href="16925007307182.html" 
	        title="Next Post: 2.6. Map - TreeSet & TreeMap 源码解析">2.6. Map - TreeSet & TreeMap 源码解析 &raquo;</a>
	    
	</div>
  </div>
</div>

<div class="row">
<div style="padding:0px 0.93em;" class="share-comments">

</div>
</div>
<script type="text/javascript">
	$(function(){
		var currentURL = '16924372183713.html';
		$('#side-nav a').each(function(){
			if($(this).attr('href') == currentURL){
				$(this).parent().addClass('active');
			}
		});
	});
</script>  
</div></div>


<div class="page-bottom">
  <div class="row">
  <hr />
  <div class="small-9 columns">
  <p class="copyright">Copyright &copy; 2015
Powered by <a target="_blank" href="http://www.mweb.im">MWeb</a>,&nbsp; 
Theme used <a target="_blank" href="http://github.com">GitHub CSS</a>.</p>
  </div>
  <div class="small-3 columns">
  <p class="copyright text-right"><a href="#header">TOP</a></p>
  </div>
   
  </div>
</div>

        </section>
      </div>
    </div>
    
    
    <script src="asset/js/foundation.min.js"></script>
    <script src="asset/js/foundation/foundation.offcanvas.js"></script>
    <script>
      $(document).foundation();

     
    </script>
    


  </body>
</html>
